/**

	Huffman.c
	=========
	
	Huffman code
	
**/



/**

   Includes
   --------

   - stdio.h    : printf
   - stdlib.h   : malloc, free, qsort, NULL
   - string.h   : strings manipulation
   - bitfield.h : bitfield manipulation
   - freq.h     : freq, FREQ_LEN
   - huffman.h  : self header

**/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <bitfield.h>
#include "freq.h"
#include "huffman.h"




/**

   Function: int huff_compare(const void* p1, const void* p2)
   ----------------------------------------------------------

   Compare function for qsort.
   Compare `struct huff_tree` `freq` field in reverse order

**/ 


static int huff_compare(const void* p1, const void* p2)
{
  float res;
  struct huff_node** a = (struct huff_node**)p1;
  struct huff_node** b = (struct huff_node**)p2;

  /* Reverse order */
  res = -( (*a)->freq - (*b)->freq );

  /* No equality for float, so use 'if' */
  if ( res > 0 )
    {
      return 1;
    }
  else if ( res < 0 )
    {
      return -1;
    }
  else
    {
      return 0;
    }

}



/**

   Function: void huff_node_delete(struct huff_node* t)
   ----------------------------------------------------

   Recursively delete/release huffman nodes

**/


static void huff_node_delete(struct huff_node* t)
{
  if (t != NULL)
    {
      huff_node_delete(t->left);
      huff_node_delete(t->right);
      free(t);
    }
  return;
}



/**

   Function: int huff_make_code(struct huff_tree* t, struct bitfield* bf)
   ----------------------------------------------------------------------

   Fill `huff_code` array

**/

static int huff_make_code(struct huff_tree* tree, struct huff_node* t,struct bitfield* bf)
{
  /* Leaf */
  if ( (t->left == NULL) && (t->right == NULL) )
    {      
      tree->code[(unsigned int)t->c] = *bf;
    }
  else
    {
      struct bitfield* bf_left;
      struct bitfield* bf_right;

      /* Clone bitfield for left trip */
      bf_left = bf_create(bf);
      if (bf_left == NULL)
	{
	  bf_delete(bf);
	  return EXIT_FAILURE;
	}

      /* Clone bitfield for right trip */
      bf_right = bf_create(bf);
      if (bf_right == NULL)
	{
	  bf_delete(bf_left);
	  bf_delete(bf);
	  return EXIT_FAILURE;
	}

      /* We dont need bf anymore */
      bf_delete(bf);

      /* Set last bit accordingly */
      bf_set(bf_left,bf_left->n);
      bf_unset(bf_right,bf_right->n);
      
      /* Recurse */
      if (huff_make_code(tree,t->left, bf_left) == EXIT_SUCCESS)
      	{
      	  return huff_make_code(tree,t->right, bf_right);
      	}
        else
      	{
      	  return EXIT_FAILURE;
      	}

    }
  
  return EXIT_SUCCESS;
}




/**

   Function: struct bitfield* huff_encode(char* str, struct huff_tree* tree)
   -------------------------------------------------------------------------

   Encode `str` via huffman code

**/


struct bitfield* huff_encode(char* str, struct huff_tree* tree)
{
  size_t n;
  struct bitfield* bf;
  int i,j;

  n = strlen(str);
  if (n)
    {
      /* Create bitfield */
      bf = bf_create(NULL);
      if (bf == NULL)
	{
	  return NULL;
	}
      
      /* Iterate through characters */
      for(i=0; i<n; i++)
	{
	  /* Iterate through bits code */
	  for(j=0;j<tree->code[(unsigned int)str[i]].n;j++)
	    {
	      /* Set or unset bit according to current character encoding */
	      if ( bf_isset(&tree->code[(unsigned int)str[i]],j) )
		{
		  bf_set(bf,bf->n);
		}
	      else
		{
		  bf_unset(bf,bf->n);
		}
	      
	    }
	}
  
      return bf;
    }
  
  return NULL;
  
}



/**

   Function: struct huff_tree huff_create(void)
   --------------------------------------------

   Create huffman tree

**/


struct huff_tree* huff_create(void)
{
	int n = FREQ_LEN;
	int i;
	struct huff_tree* tree;
	struct huff_node* node;
	struct huff_node* huff_array[FREQ_LEN];
	struct bitfield* huff_code;

	/* Allocate tree */
	tree = (struct huff_tree*)malloc(sizeof(struct huff_tree));
	if ( tree == NULL )
	  {
	    return NULL;
	  }
	tree->len = FREQ_LEN;

	/* Allocate huffman code */
	huff_code = (struct bitfield*)malloc(FREQ_LEN*sizeof(struct bitfield));
	if (huff_code == NULL)
	  {
	    goto err0;
	  }

	/* Initialize `huff_array` and `huff_code` */
	for(i=0;i<FREQ_LEN;i++)
	  {
	    /* Allocate node tree */
	    node = (struct huff_node*)malloc(sizeof(struct huff_node));
	    if ( node == NULL )
	      {
		goto err1;
	      }
	    
	    /* Fill fields */
	    node->c = (unsigned char)i;
	    node->freq = freq[i];
	    node->left = NULL;
	    node->right = NULL;

	    /* Register node */
	    huff_array[i] = node;

	  }

	/* Sort descending `huff_array` */
	qsort(huff_array,n,sizeof(*huff_array),huff_compare);
	
	/* Create huffman tree */
	while( n > 1 )
	{
	  /* Allocate new node for merging */
	  node = (struct huff_node*)malloc(sizeof(struct huff_node));
	  if ( node == NULL )
	    {
	      goto err2;
	    }
	  
	  /* Merge two smaller frequencies into one node */
	  node->freq = huff_array[n-2]->freq + huff_array[n-1]->freq;
	  node->left = huff_array[n-2];
	  node->right = huff_array[n-1];

	  /* Register new node and update count */
	  huff_array[n-2] = node;
	  n--;

	  /* Reorder array */
	  qsort(huff_array,n,sizeof(*huff_array),huff_compare);

	}
	
	/* `huff_array[0]` is now huffman tree root */
	tree->root = huff_array[0];
	tree->code = huff_code;

	if (huff_make_code(tree,tree->root,NULL) != EXIT_SUCCESS)
	  {
	    goto err2;
	  }

	
	return tree;

 err2:
	/* Free huffman nodes */
	for(i=0;i<FREQ_LEN;i++)
	  {
	    huff_node_delete(huff_array[i]);
	  }

 err1:
	/* Free huffman code */
	free(huff_code);

 err0:

	/* Free huffman tree */
	free(tree);

	return NULL;

}


/**

   Function: int huff_delete(struct huff_tree* tree)
   -------------------------------------------------

   Release allocated object needed for huffman code

**/

int huff_delete(struct huff_tree* tree)
{
  /* Free huffman code */
  free(tree->code);
  	
  /* Free huffman nodes */
  huff_node_delete(tree->root);

  /* Free tree */
  free(tree);

  return EXIT_SUCCESS;
}
